package leetcode.code1095;

import leetcode.helper.H;

public class Solution {
	int len;

	public int findInMountainArray(int target, MountainArray mountainArr) {
		len = mountainArr.length();
		int mid = f(mountainArr);
		if (mountainArr.get(mid) == target) {
			return mid;
		}
		int ans = f1(mountainArr, 0, mid - 1, target);
		if (ans != -1) {
			return ans;
		}
		return f2(mountainArr, mid + 1, len - 1, target);
	}

	private int f1(MountainArray mount, int l, int r, int target) {
		while (l <= r) {// while写成if几个意思
			int mid = ((r - l) >> 1) + l;
			int num = mount.get(mid);
			if (num == target) {
				return mid;
			}
			if (num > target) {// num写成mid几个意思
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		return -1;
	}

	private int f2(MountainArray mount, int l, int r, int target) {
		while (l <= r) {
			int mid = ((r - l) >> 1) + l;
			int num = mount.get(mid);
			if (num == target) {
				return mid;
			}
			if (num > target) {
				l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
		return -1;
	}

	private int f(MountainArray mount) {
		int l = 0, r = len - 1;
		while (l <= r) {
			int mid = ((r - l) >> 1) + l;
			int num = mount.get(mid);
			int L = mid - 1 == -1 ? -1 : mount.get(mid - 1);
			int R = mid + 1 == len ? -1 : mount.get(mid + 1);
			if (num > L && num > R) {
				return mid;
			}
			if (L < num && num < R) {
				l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
		return -1;
	}

	public static void main(String[] args) {
		
//		[1,2,3,4,5,3,1]
//				3
//				[0,1,2,4,2,1]
//				3
//				[3,5,3,2,0]
//				0

		int[] arr = H.str2array3("[3,5,3,2,0]");
//		int[] arr = H.str2array3("[1,2,3,4,5,3,1]");
		Solution so = new Solution();
		int ans = so.findInMountainArray(3, new MountainArray() {

			@Override
			public int length() {
				// TODO Auto-generated method stub
				return arr.length;
			}

			@Override
			public int get(int index) {

				return arr[index];
			}
		});

		System.out.println(ans);
	}
}
